/* 计算二叉树的带权路径长度（叶子节点） */
#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 计算带权路径长度 -- 方法一
int fun(BTNode *p)
{
  // 创建队列
  BTNode *que[maxsize];
  int front = 0, rear = 0;
  
  // 记录带权路径长度、该层最后一个结点的序号、所在层次
  int wpl = 0, last = 1, deep = 0;
  
  // 根结点进队列
  que[++rear] = p;
  
  // 层次遍历
  while (front != rear)
  {
    // 结点出队列
    p = que[++front];
    
    // 如果是叶子结点
    if (!p->lchild && !p->rchild)
      wpl += deep * (p->data - '0'); // 更新带权路径长度
    
    // 左孩子结点进队
    if (p->lchild != NULL)
      que[++rear] = p->lchild;
    
    // 右孩子结点进队
    if (p->rchild != NULL)
      que[++rear] = p->rchild;
    
    // 到达该层的最后一个结点
    if (front == last)
    {
      deep++; // 更新深度
      last = rear; // 更新一层中最后一个结点的序号
    }
  }
  
  // 返回带权路径长度
  return wpl;
}

// 计算带权路径长度 -- 方法二
int fun2(BTNode *p, int deep)
{
  int A, B;
  
  // 二叉树为空
  if (p == NULL)
    return 0; // 带权路径长度为0
  
  // 二叉树只有一个根结点
  if (!p->lchild && !p->rchild)
    return deep * (p->data - '0'); // 直接返回带权路径长度
  
  // 左子树的带权路径长度，deep记录根结点所在深度
  A = fun2(p->lchild, deep + 1);
  
  // 右子树的带权路径长度，deep记录根结点所在深度
  B = fun2(p->rchild, deep + 1);
  
  // 返回带权路径长度
  return A + B;
}

// 计算带权路径长度 -- 方法三
int fun3(BTNode *p, int deep)
{
  int A, B;
  
  // 二叉树为空
  if (p == NULL)
    return 0;
  
  // 二叉树只有一个根结点，直接返回带权路径长度
  if (!p->lchild && !p->rchild)
    return (p->data - '0') * deep;
  
  // 计算左右子树的带权路径长度，deep记录根结点所在深度
  ++deep;
  A = fun3(p->lchild, deep);
  B = fun3(p->rchild, deep);
  --deep;
  return A + B;
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 计算带权路径长度
  int x = 0;
  cout << "wpl:" << fun3(T, x);
  return 0;
}